
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */

    class creatTreeByPostAndIn {
        public static class TreeNode {
            int val;
            TreeNode right;
            TreeNode left;

            TreeNode() {
            }

            TreeNode(int val) {
                this.val = val;
            }

            TreeNode(int val, TreeNode left, TreeNode right) {
                this.val = val;
                this.left = left;
                this.right = right;
            }
        }

        public int postIndex = 0;

        //public int postIndex = 0;
        //创建二叉树
        public TreeNode buildTree(int[] inorder, int[] postorder) {

            postIndex = postorder.length - 1;
            //调用函数
            return buildTreeChild(postorder, inorder, 0, inorder.length - 1);

        }


        public TreeNode buildTreeChild(int[] postorder, int[] inorder, int inbegin, int inend) {
            //防止数组越界
            if (inbegin > inend) {
                return null;
            }
            //1.根节点
            TreeNode root = new TreeNode(postorder[postIndex]);

//        2/求根节点下标
            int rootIndex = findRootIndex(inorder, inbegin, inend, postorder[postIndex]);
            postIndex--;

            //3.创建左树
            root.right = buildTreeChild(postorder, inorder, rootIndex + 1, inend);
            // 4.创建右树
            root.left = buildTreeChild(postorder, inorder, inbegin, rootIndex - 1);

            return root;
        }

        //5.索引下标查找
        private int findRootIndex(int[] inorder, int inbegin, int inend, int key) {
            for (int i = inbegin; i <= inend; i++) {
                if (inorder[i] == key) {
                    return i;
                }
            }
            return -1;
        }
    }

